package tests;

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

public class MinimumSpanningTree {

	Queue<UndirectedGraph.Edge> priorityQueue = null;
	private final UndirectedGraph G;
	/* Test method for the class. */
	
	public MinimumSpanningTree(UndirectedGraph g){
		this.G = g;
		
		//Comparator<UndirectedGraph.Edge> E = G.EdgeComparator();
		
		// instansiate the 
		priorityQueue = new PriorityQueue<UndirectedGraph.Edge>(G.getSize(), ( G.new EdgeComparator()));
	}
	/* Add the current node's unvisited neighbors to the priority queue. */
	private void addNeigborsToPQ(int index, Iterator<UndirectedGraph.Edge> it){
		
		G.setVisited(index);

		/* For each neighbor of the current node which is 
		 * NOT already on the priority queue...*/
		while(it.hasNext()) {
			UndirectedGraph.Edge nextNeighbor = it.next();			
			if(!priorityQueue.contains(nextNeighbor))
			{
				/* Add the edge. */
				if(!G.getVisited(nextNeighbor.getOppositeVertex(index)))
					priorityQueue.add(nextNeighbor);
			}
		}
	}
	/*
	 * Run the algorithm, based on a random selected node
	 */
	public double runMST(String startNode) {
		
		double totalDist = 0;
		
		// Add the startNode's neighbors to the priority queue.
		System.out.println("Starting MST search from " + startNode);
		int currNodeIndex = G.getVertexIndex(startNode);
		this.addNeigborsToPQ(currNodeIndex, G.getEdgeIterator(currNodeIndex));
		
		/* Main loop for the algorithm. 
		 * 	Pop (V-1) edges off the priority queue. */ 
		for(int i = 0; i < G.getSize(); i++) {

			System.out.println("The currentNodeIndex: " + currNodeIndex);
			
			// Pop the lowest weight edge off the PQ
			UndirectedGraph.Edge cheapestEdge = priorityQueue.remove();
			if(!G.getVisited(cheapestEdge.getV()))
				currNodeIndex = cheapestEdge.getV();
			else if(!G.getVisited(cheapestEdge.getW()))
				currNodeIndex = cheapestEdge.getW();
			else{
				System.out.println("MinimumSpanningTree.runMST(): Neither node was unvisited. ");
				continue;
			}
			
			System.out.print("The cheapest edge on the PQ was " + cheapestEdge.toString());
			System.out.print(" (" + G.getVertexString(cheapestEdge.getV()) + ") |");
			System.out.println(" (" + G.getVertexString(cheapestEdge.getW()) + ")");
			
			totalDist += cheapestEdge.getWeight();

			System.out.println("Total Distance: " + totalDist);
			
			this.addNeigborsToPQ(currNodeIndex, G.getEdgeIterator(currNodeIndex));
		}
		return totalDist;
	}
}

